import java.util.Stack;

public class Calculator {

    /**
     * 计算一个四则运算表达式
     */

    public int calculator(String s) {
        String[] strs = getPostfixExpression(s).split(" ");
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        for (String str : strs) {
            // 如果是操作符，从堆栈获取两个值，进行运算
            if (str.length() == 1 && isOperator(str.charAt(0))) {
                int num2 = stack.pop();
                int num1 = stack.pop();
                stack.push(calculate2Numbers(num1, num2, str.charAt(0)));
            } else {    // 如果是数字，压入堆栈
                stack.push(Integer.parseInt(str));
            }
        }
        return stack.pop();
    }


    public String getPostfixExpression(String s) {
        // 创建堆栈
        Stack<Character> stack = new Stack<>();
        String postfixExp = "";

        // 遍历表达式的每一个字符
        for (int i = 0; s != null && i < s.length(); i++) {
            char ch = s.charAt(i);
            if (' ' != ch) {    // 当前字符不为空 时的操作
                if (isLeftBracket(ch)) {    // 是左括号，压栈
                    stack.push(ch);
                } else if (isRightBracket(ch)) { // 是右括号，将所有操作符出栈，直到遇到一个左括号，并将这个左括号丢弃
                    char topOperator = stack.pop();
                    while (!isLeftBracket(topOperator)) {
                        postfixExp += (topOperator + " ");    // 使用空格 隔开
                        topOperator = stack.pop();
                    }
                } else if (isOperator(ch)) {    // 是操作符，要判断优先级，再决定是否需要入栈
                    /*
                     * 如果栈为空，直接进栈。 如果栈非空，则需要将栈顶运算符的优先级和要入栈的运算符的优先级进行比较
                     * 将栈中比要入栈的运算符优先级高的运算符都出栈，然后将该运算符入栈
                     */
                    if (!stack.isEmpty()) { // 如果栈非空
                        Character topOperator = stack.peek();
                        while (topOperator != null && priority(topOperator) >= priority(ch)) {
                            postfixExp += (stack.pop() + " ");
                            if (!stack.isEmpty()) {
                                topOperator = stack.peek();
                            } else {
                                break;
                            }
                        }
                    }
                    // 将当前操作符 压栈
                    stack.push(ch);
                } else {
                    if (i > 0 && isNumber(s.charAt(i - 1))) {
                        postfixExp = postfixExp.substring(0, postfixExp.length() - 1) + ch + " ";
                    } else {
                        postfixExp += ch + " ";
                    }
                }
            }
        }

        while (!stack.isEmpty()) {
            postfixExp += (stack.pop() + " ");
        }

        // 去除表达式中的最后一个空格
//		postfixExp = postfixExp.substring(0, postfixExp.length() - 1);
        postfixExp = postfixExp.trim();
        return postfixExp;
    }

    /**
     * 运算符优先级比较
     */
    public int priority(char charValue) {
        switch (charValue) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
            case '%':
                return 2;
            case '^':
                return 3;
        }
        return 0;
    }

    /**
     * 判断是否是操作符
     */
    public boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^' || ch == '%';
    }

    /**
     * 判断是否是左括号
     */
    public boolean isLeftBracket(char ch) {
        return ch == '(';
    }

    /**
     * 判断是否是右括号
     */
    public boolean isRightBracket(char ch) {
        return ch == ')';
    }

    /**
     * 判断是否是数字
     */
    public boolean isNumber(char ch) {
        return ch >= '0' && ch <= '9';
    }

    /**
     * 两数的运算操作
     */
    public Integer calculate2Numbers(int num1, int num2, char operator) {
        switch(operator) {
            case '+':
                return num1 + num2;
            case '-':
                return num1 - num2;
            case '*':
                return num1 * num2;
            case '/':
                return num1 / num2;
            case '%':
                return num1 % num2;
            case '^':
                return num1 ^ num2;
        }
        return null;
    }


    public static void main(String[] args) {
        String s = "9+(3-1)*3+10/2";
        Calculator calculator = new Calculator();
        System.out.println(calculator.calculator(s));
    }
}

